package 面试经典150题.链表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * @author tmh
 * @date 2024/6/27 21:36
 * @description
 */
public class T215数组中的第K个最大元素 {
    //直接调用库函数--可以ac
//    public int findKthLargest(int[] nums, int k) {
//        Arrays.sort(nums);
//        return nums[nums.length-k];
//    }

    public int findKthLargest(int[] nums, int k) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) {
            numList.add(num);
        }
        return quickSort(numList,k);

/*        作者：Krahets
        链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/2361969/215-shu-zu-zhong-de-di-k-ge-zui-da-yuan-d786p/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
    }

    public int quickSort(List<Integer> nums, int k) {
        //基于快排的快速排序
        //随机选择基准数字
        int p = nums.get(new Random().nextInt(nums.size()));
        //将 大于 小于 等于的元素分别放入三个数组
        List<Integer> small = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> big = new ArrayList<>();
        for (Integer num : nums) {
            if (num < p) {
                small.add(num);
            }
            if (num > p) {
                big.add(num);
            }
            if (num==p){
                equal.add(num);
            }

        }
        //当第k个大的元素在big数组中==>k<=big.size()，对big数组进行递归划分
        if (k <= big.size()) {
            quickSort(big, k);
        }
        //当第k个大的元素在small数组里面==》k的值要大于equal数组的长度+big数组的长度
        if (k > equal.size() + big.size()) {
            //这里第二个参数需要打一个括号，不然会报错
            quickSort(small, k - (equal.size() + big.size()));
        }
        //当第k个大的元素在equal中，返回p
        return p;

    }

//    class Solution {
//public:
//    int findKthLargest(vector<int>& nums, int k) {
//        return quickSelect(nums, k);
//    }
//    int quickSelect(vector<int>& nums, int k) {
//        // 基于快排的快速选择
//        // 随机选择基准数字
//        int p = nums[rand() % nums.size()];
//        // 将大于等于小于的元素分别放入三个数组
//        vector<int> big, equal, small;
//        for (int a : nums) {
//            if (a < p) small.push_back(a);
//            else if (a == p) equal.push_back(a);
//            else big.push_back(a);
//        }
//        // 第k大元素在big中, 递归划分
//        if (k <= big.size()) {
//            return quickSelect(big, k);
//        }
//        // 第k大元素在small中, 递归划分
//        if (big.size() + equal.size() < k) {
//            return quickSelect(small, k - (big.size() + equal.size()));
//        }
//        // 第k大元素在equal中, 返回p
//        return p;
//    }
//};
}
